public class Kmp
{
    public static int KMP(String str,String sub) {
        if (str==null || sub==null) return -1;

        int lenStr=str.length();
        int lenSub=sub.length();

        int i=0;
        int j=0;

        int[] next=new int[lenSub];
        getNext(next,sub);

        while (i<lenStr && j<lenSub) {
            if ( str.charAt(i)==sub.charAt(j)) {
                i++;
                j++;
            } else if(next[j]==-1){//j==0;sub中比对的位置已经无法往前跳了
                i++;//str中的i++
            }else {
                j=next[j];
            }
        }
        if (j>=lenSub) {
            return i-j;
        }

        return -1;
    }


    public static void getNext(int[] next,String sub){
        if (sub==null) return;

        next[0]=-1;
        next[1]=0;
        //人为规定-1,0，所以i从2小标开始
        int i;
        for(i=2;i<sub.length();i++){
            int cur=next[i-1];
            while (cur!=-1&&next[i-1]!=next[cur]){
                cur=next[cur];
            }
            next[i]=cur+1;
        }
    }

    public static void main(String[] args) {
//        System.out.println(KMP("kdjsls","djs"));
        System.out.println(KMP("kdjsls","djsa"));
        System.out.println(KMP("kdjsls","kd"));

    }
}
